#include "binaryTree.h"
#define MAX_QUEUE_SIZE 100
TREE *create_treeDLR()
{
    type temp;
    IN(temp);
    if ('#' == temp)
    {
        return NULL;
    }
    TREE *root = (TREE *)malloc(sizeof(TREE));
    ERROR_CHECK(NULL, root, "malloc");
    root->data = temp;
    root->lchild = create_treeDLR();
    root->rchild = create_treeDLR();
    return root;
}
void DLR_show(TREE *root)
{
    if (NULL == root)
    {
        return;
    }
    OUT(root->data);
    DLR_show(root->lchild);
    DLR_show(root->rchild);
}
void LDR_show(TREE *root)
{
    if (NULL == root)
    {
        return;
    }

    LDR_show(root->lchild);
    OUT(root->data);
    LDR_show(root->rchild);
}
void LRD_show(TREE *root)
{
    if (NULL == root)
    {
        return;
    }
    LRD_show(root->lchild);
    LRD_show(root->rchild);
    OUT(root->data);
}
typedef struct QueueNode
{
    TREE *treeNode;
    struct QueueNode *next;
} QueueNode;
typedef struct
{
    QueueNode *front;
    QueueNode *rear;
} Queue;
void enqueue(Queue *q, TREE *node)
{
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->treeNode = node;
    newNode->next = NULL;
    if (q->rear)
    {
        q->rear->next = newNode;
    }
    q->rear = newNode;
    if (!q->front)
    {
        q->front = newNode;
    }
}
TREE *dequeue(Queue *q)
{
    if (!q->front)
        return NULL;
    QueueNode *temp = q->front;
    TREE *node = temp->treeNode;
    q->front = q->front->next;
    if (!q->front)
    {
        q->rear = NULL;
    }
    free(temp);
    return node;
}
void level_showQueue(TREE *root)
{
    if (NULL == root)
    {
        return;
    }

    Queue q = {NULL, NULL};
    enqueue(&q, root);

    while (q.front)
    {
        TREE *node = dequeue(&q);
        OUT(node->data);

        if (node->lchild)
        {
            enqueue(&q, node->lchild);
        }
        if (node->rchild)
        {
            enqueue(&q, node->rchild);
        }
    }
}
void level_showArry(TREE *root)
{
    if (NULL == root)
    {
        return;
    }

    TREE *queue[MAX_QUEUE_SIZE];
    int front = 0, rear = 0;

    queue[rear++] = root; // 入队根节点

    while (front < rear)
    {
        TREE *node = queue[front++]; // 出队
        OUT(node->data);

        if (node->lchild)
        {
            if (rear < MAX_QUEUE_SIZE)
            {
                queue[rear++] = node->lchild; // 入队左子节点
            }
        }
        if (node->rchild)
        {
            if (rear < MAX_QUEUE_SIZE)
            {
                queue[rear++] = node->rchild; // 入队右子节点
            }
        }
    }
}
void levelShow(TREE *root){

    if (NULL == root)
    {
        return;
    }
    TREE *queue[MAX_QUEUE_SIZE];
    int front  = 0,rear = 0;
    queue[rear++] = root;
    while(front < rear){
        TREE *node = queue[front++];
        OUT(node->data);//OUT(queue[front++]->data)
        if (node->lchild) //if(queue[front]->lchild)
        {
            queue[rear++] = node->lchild;//queue[rear++] = queue[front]->lchild
        }
        if (node->rchild)//if(queue[front]->rchild)
        {
            queue[rear++] = node->rchild;//queue[rear++] = queue[front]->rchild
        }
    }
    
}

void freeTreeLRD(TREE **root)
{

    if (NULL == *root)
    {
        return;
    }
    freeTreeLRD(&(*root)->lchild);
    freeTreeLRD(&(*root)->rchild);
    free(*root);
    *root = NULL;
}
